//如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。 
//
// 给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 20
//输出：19
//解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。
// 
//
// 示例 2： 
//
// 
//输入：n = 5
//输出：5
//解释：1 到 5 所有整数都是特殊整数。
// 
//
// 示例 3： 
//
// 
//输入：n = 135
//输出：110
//解释：从 1 到 135 总共有 110 个整数是特殊整数。
//不特殊的部分数字为：22 ，114 和 131 。 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 2 * 10⁹ 
// 
// Related Topics数学 | 动态规划 
//
// 👍 36, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.Arrays;

class CountSpecialIntegers {
    public static void main(String[] args) {
        Solution solution = new CountSpecialIntegers().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        char[] s;
        int[][] memo;

        // 数位DP，和1012一摸一样
        public int countSpecialNumbers(int n) {
            s = String.valueOf(n).toCharArray();
            int m = s.length;
            memo = new int[m][1024];
            for (int i = 0; i < m; i++) {
                Arrays.fill(memo[i], -1);
            }

            // 求每个数字都是不相同的
            return f(0, 0, true, false);
        }

        // 表示没有重复的字数的个数
        // mask 大小为 1024，长度为 10 位，记录 0 - 9 选择的情况，若 i 已选择，则 mask 中第 i 位为 1
        public int f(int i, int mask, boolean isLimit, boolean isNum) {
            if (i == s.length) return isNum ? 1 : 0;
            if (!isLimit && isNum && memo[i][mask] != -1) return memo[i][mask];
            int down = isNum ? 0 : 1;
            int up = isLimit ? s[i] - '0' : 9;
            int res = isNum ? 0 : f(i + 1, mask, false, false);
            for (int j = down; j <= up; j++) {
                if (((mask >> j) & 1) == 0) {
                    res += f(i + 1, mask | (1 << j), isLimit && j == up, true);
                }
            }

            if (!isLimit && isNum) memo[i][mask] = res;
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
